Background: In the anaerobic pathway of cobalamin (vitamin B12) synthesis, the CbiT enzyme plays two roles, as a cobalt-precorrin-7 C15-methyltransferase and a C12-decarboxylase, to produce the intermediate, cobalt-precorrin 8. Results: The primary structure of the hypothetical protein MJ0391, from Methanocaldococcus jannaschii, suggested that MJ0391 is a putative CbiT. Here, we report the crystal structure of MJ0391, solved by the MAD procedure and refined to final R-factor and R-free values of 19.8 & 27.3%, respectively, at 2.3 Å resolution. The asymmetric unit contains two NCS molecules, and the intact tetramer generated by crystallographic symmetry may be functionally important. The overall tertiary structure and the tetrameric arrangements are highly homologous to those found in MT0146/CbiT from Methanobacterium thermoautotrophicum. Conclusions: The conservation of functional residues in the binding site for the co-factor, AdoMet, and in the putative precorrin-7 binding pocket suggested that MJ0391 may also possess CbiT activity. The putative function of MJ0391 is discussed, based on structural homology.